Feature #6: Maximum Users

Implement the "Maximum Number of Users" feature for our "Cellular Operator AT&T" project.

Description#

On a busy intersection with heavy vehicular and pedestrian traffic, the operator deploys a base station. The number of users connected to that base station keeps changing rapidly, as people enter and leave its coverage area. The base station quickly dumps the current number of users to a list every 1 ms.

The operator wants to analyze the data to improve coverage for its users. However, the data contains rapid variations that don’t carry useful information from a network management perspective. To deal with the variation, the operator wants to find the maximum number of users connected to the base station in every k ms sliding window.

Given a list of values, we need to create a sliding window of size k (shown in red) and find the max in each sliding window. Different sliding windows in the given list are shown in separate rows in the following illustration, along with the maximum value in the sliding window.

4
4
7
7
12
12
16
16
8
8
3
3
13
13
20
20
5
5
9
9
22
22
2
2
4
4
7
7
12
12
16
16
8
8
3
3
13
13
20
20
5
5
9
9
22
22
2
2
4
4
7
7
12
12
16
16
8
8
3
3
13
13
20
20
5
5
9
9
22
22
2
2
4
4
7
7
12
12
16
16
8
8
3
3
13
13
20
20
5
5
9
9
22
22
2
2
4
4
7
7
12
12
16
16
8
8
3
3
13
13
20
20
5
5
9
9
22
22
2
2
4
4
7
7
12
12
16
16
8
8
3
3
13
13
20
20
5
5
9
9
22
22
2
2
MAX
[Not supported by viewer]
16
[Not supported by viewer]
20
20
20
20
20
20
22
22
22
22
Maximum number of users

Solution#

Here, we will find the maximum number of users who are connected to the base station in the selected k millisecond windows. Each entry in the array will show the number of users who are connected to the base station in the 1 ms window.

Here is how we will implement this feature:

  1. We are given an array of integers.

  2. If the value at the current index is less than the value at the previous index of the array or all the value(s) of the index(es) in mqueue, then we will push the current index to the mqueue. Otherwise, we will perform the pop operation.

  3. During the loop execution, if the mqueue value (index) at zero index is equal to the i-k, then we will perform the shift operation in the mqueue.

  4. If the index of the given array is greater than or equal to the window slide length (k), then we will push the maximum value of the mqueue to the result array.

This way, the result array will contain the maximum number for each window slide (k).

The following illustrations show us how the solution given above will work:

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

1 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

2 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

3 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

4 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

5 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

6 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

7 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

8 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

9 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

10 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

11 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

12 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

13 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

14 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

15 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

16 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

17 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

18 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

19 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

20 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

21 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

22 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

23 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

24 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

25 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

26 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

27 of 28

Created with Fabric.js 3.6.6
Obtain maximum users using monotonic queue

28 of 28

Let’s look at the solution code below:

Maximum users

Complexity measures#

Time complexity Space complexity
O(n)O(n) O(k)O(k)

Time complexity#

Here, we are iterating the outer for loop n times and the inner while loop k times. Here, n is the size of the given array, and k is the size of the sliding window, which is constant. Therefore, the time complexity will be O(n)O(n).

Space complexity#

The space complexity will be O(k)O(k), because we need to store a maximum of k values in the mqueue.

Feature #5: Densest Deployment

Feature #7: Maximum Contiguous Area